class LinkedList:
    class _Node:
        def __init__(self, data, next):
            self._data = data
            self._next = next

    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0
    
    def __repr__(self):
        node = self._head
        nodes = []
        while node is not None:
            nodes.append(node._data)
            node = node._next
        nodes.append("None")
        return " -> ".join(nodes)
    
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size == 0

    def get_head(self):
        return self._head._data if self._head is not None else 'Empty'
    
    def get_tail(self):
        return self._tail._data if self._tail is not None else 'Empty'

    def add_tail(self,e):
        """
        Add an element to the back of the tail
        """
        newest = self._Node(e, None)
        if self.is_empty():
            self._head = newest
        else:
            self._tail._next = newest
        self._tail = newest
        self._size += 1

    def pop_tail(self):
        """
        Remove and return the last element
        """
        if self.is_empty():
            raise Empty("It's Empty")
        if self._size == 1:
            answer = self._head
            self._head = None
            self._tail = None
            self._size -= 1
            return answer
        current = self._head
        while current._next is not self._tail:
            current = current._next
        answer = self._tail
        current._next = None
        self._tail = current
        self._size -= 1
        return answer
    
    def pop_head(self):
        """
        Remove and return the first element
        """
        if self.is_empty():
            raise Empty("It's Empty")
        answer = self._head = self._head._next
        self._size -= 1
        if self.is_empty():
            self._tail = None
        return answer
    
    def add_head(self,e):
        """
        Add an element to the front of the head
        """
        newest = self._Node(e, self._head)
        self._head = newest
        if self.is_empty():
            self._tail = newest
        self._size += 1
    
    def search(self, e):
        """
        Search for an element in the linked list
        """
        current = self._head
        while current is not None:
            if current._data == e:
                return True
            current = current._next
        return False

class Empty(Exception):
    def __init__(self, *args):
        super().__init__(*args)

if __name__ == '__main__':
    ll = LinkedList()

    ll.add_tail('pomme')
    ll.add_tail('banana')
    ll.add_tail('orange')
    ll.add_tail('kiwi')
    print(ll._size)
    print(ll)
    print(ll._head._data)
    print(ll._tail._data)
    ll.pop_head()
    print(ll)
    print(ll.search('banana'))